// Copyright (c) 2005-2008, Simon Howard
// Permission to use, copy, modify, and/or distribute this software
// for any purpose with or without fee is hereby granted, provided
// that the above copyright notice and this permission notice appear
// in all copies.
// THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL
// WARRANTIES WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE
// AUTHOR BE LIABLE FOR ANY SPECIAL, DIRECT, INDIRECT, OR
// CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM
// LOSS OF USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT,
// NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN
// CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.

#![allow(dead_code)]

use std::cmp::Ordering;
use std::fmt::Debug;
use std::mem;

/// A node in the singly linked list.
#[derive(Debug)]
pub struct SListEntry<T> {
    data: T,
    next: Option<Box<SListEntry<T>>>,
}

impl<T> SListEntry<T> {
    /// Creates a new list node.
    pub fn new(data: T) -> Self {
        SListEntry { data, next: None }
    }

    /// Returns a reference to the data in the node.
    pub fn data(&self) -> &T {
        &self.data
    }

    /// Returns a mutable reference to the data in the node.
    pub fn data_mut(&mut self) -> &mut T {
        &mut self.data
    }

    /// Returns the next node in the list.
    pub fn next(&self) -> Option<&SListEntry<T>> {
        self.next.as_deref()
    }

    /// Returns a mutable reference to the next node in the list.
    pub fn next_mut(&mut self) -> Option<&mut SListEntry<T>> {
        self.next.as_deref_mut()
    }

    /// Sets the next node in the list.
    pub fn set_next(&mut self, next: Option<Box<SListEntry<T>>>) {
        self.next = next;
    }
}

/// A singly linked list.
#[derive(Debug)]
pub struct SList<T> {
    head: Option<Box<SListEntry<T>>>,
    length: usize,
}

impl<T> SList<T> {
    /// Creates a new empty list.
    pub fn new() -> Self {
        SList {
            head: None,
            length: 0,
        }
    }

    /// Appends a new element to the end of the list.
    pub fn append(&mut self, data: T) {
        let new_node = Box::new(SListEntry::new(data));
        let mut current = &mut self.head;

        while let Some(ref mut node) = current {
            current = &mut node.next;
        }

        *current = Some(new_node);
        self.length += 1;
    }

    /// Prepends a new element to the beginning of the list.
    pub fn prepend(&mut self, data: T) {
        let new_node = Box::new(SListEntry::new(data));
        new_node.set_next(self.head.take());
        self.head = Some(new_node);
        self.length += 1;
    }

    /// Returns the length of the list.
    pub fn length(&self) -> usize {
        self.length
    }

    /// Returns the nth entry in the list.
    pub fn nth_entry(&self, index: usize) -> Option<&SListEntry<T>> {
        let mut current = self.head.as_deref();
        for _ in 0..index {
            current = current?.next();
        }
        current
    }

    /// Returns the nth data in the list.
    pub fn nth_data(&self, index: usize) -> Option<&T> {
        self.nth_entry(index).map(|entry| entry.data())
    }

    /// Removes the nth entry from the list.
    pub fn remove_nth(&mut self, index: usize) -> Option<T> {
        if index == 0 {
            let node = self.head.take()?;
            self.head = node.next;
            self.length -= 1;
            return Some(node.data);
        }

        let mut current = self.head.as_mut();
        for _ in 0..index - 1 {
            current = current?.next_mut();
        }

        let node = current?.next.take()?;
        current.as_mut()?.set_next(node.next);
        self.length -= 1;
        Some(node.data)
    }

    /// Removes the first entry that matches the given data.
    pub fn remove_data<F>(&mut self, eq: F, data: &T) -> bool
    where
        F: Fn(&T, &T) -> bool,
    {
        let mut current = &mut self.head;

        while let Some(ref mut node) = current {
            if eq(&node.data, data) {
                let removed = current.take();
                *current = removed.unwrap().next;
                self.length -= 1;
                return true;
            }
            current = &mut node.next;
        }

        false
    }

    /// Sorts the list using the given comparison function.
    pub fn sort<F>(&mut self, compare: F)
    where
        F: Fn(&T, &T) -> Ordering,
    {
        let mut vec = Vec::new();
        while let Some(node) = self.head.take() {
            vec.push(node.data);
            self.head = node.next;
        }

        vec.sort_by(compare);

        let mut new_head = None;
        for data in vec.into_iter().rev() {
            let mut node = Box::new(SListEntry::new(data));
            node.set_next(new_head);
            new_head = Some(node);
        }

        self.head = new_head;
    }

    /// Converts the list to an array.
    pub fn to_array(&self) -> Vec<&T> {
        let mut array = Vec::new();
        let mut current = self.head.as_deref();

        while let Some(node) = current {
            array.push(&node.data);
            current = node.next();
        }

        array
    }
}

impl<T> Drop for SList<T> {
    fn drop(&mut self) {
        let mut current = self.head.take();
        while let Some(mut node) = current {
            current = node.next.take();
        }
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_slist_append() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&variable1));
        assert_eq!(list.nth_data(1), Some(&variable2));
        assert_eq!(list.nth_data(2), Some(&variable3));
        assert_eq!(list.nth_data(3), Some(&variable4));
    }

    #[test]
    fn test_slist_prepend() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.prepend(variable1);
        list.prepend(variable2);
        list.prepend(variable3);
        list.prepend(variable4);

        assert_eq!(list.length(), 4);
        assert_eq!(list.nth_data(0), Some(&variable4));
        assert_eq!(list.nth_data(1), Some(&variable3));
        assert_eq!(list.nth_data(2), Some(&variable2));
        assert_eq!(list.nth_data(3), Some(&variable1));
    }

    #[test]
    fn test_slist_free() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        drop(list); // Explicitly drop the list to test cleanup
    }

    #[test]
    fn test_slist_next() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let mut rover = list.nth_entry(0).unwrap();
        assert_eq!(rover.data(), &variable1);
        rover = rover.next().unwrap();
        assert_eq!(rover.data(), &variable2);
        rover = rover.next().unwrap();
        assert_eq!(rover.data(), &variable3);
        rover = rover.next().unwrap();
        assert_eq!(rover.data(), &variable4);
        assert!(rover.next().is_none());
    }

    #[test]
    fn test_slist_nth_entry() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let entry = list.nth_entry(0).unwrap();
        assert_eq!(entry.data(), &variable1);
        let entry = list.nth_entry(1).unwrap();
        assert_eq!(entry.data(), &variable2);
        let entry = list.nth_entry(2).unwrap();
        assert_eq!(entry.data(), &variable3);
        let entry = list.nth_entry(3).unwrap();
        assert_eq!(entry.data(), &variable4);
        assert!(list.nth_entry(4).is_none());
        assert!(list.nth_entry(400).is_none());
    }

    #[test]
    fn test_slist_nth_data() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.nth_data(0), Some(&variable1));
        assert_eq!(list.nth_data(1), Some(&variable2));
        assert_eq!(list.nth_data(2), Some(&variable3));
        assert_eq!(list.nth_data(3), Some(&variable4));
        assert_eq!(list.nth_data(4), None);
        assert_eq!(list.nth_data(400), None);
    }

    #[test]
    fn test_slist_length() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        assert_eq!(list.length(), 4);

        list.prepend(variable1);
        assert_eq!(list.length(), 5);

        let empty_list = SList::<i32>::new();
        assert_eq!(empty_list.length(), 0);
    }

    #[test]
    fn test_slist_remove_entry() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let entry = list.nth_entry(2).unwrap();
        list.remove_nth(2);
        assert_eq!(list.length(), 3);

        let entry = list.nth_entry(0).unwrap();
        list.remove_nth(0);
        assert_eq!(list.length(), 2);

        let empty_list = SList::<i32>::new();
        assert_eq!(empty_list.length(), 0);
    }

    #[test]
    fn test_slist_remove_data() {
        let mut list = SList::new();
        let entries = [89, 4, 23, 42, 4, 16, 15, 4, 8, 99, 50, 30, 4];

        for &entry in &entries {
            list.prepend(entry);
        }

        assert_eq!(list.length(), entries.len());

        let val = 8;
        assert!(list.remove_data(|a, b| a == b, &val));
        assert_eq!(list.length(), entries.len() - 1);

        let val = 4;
        let mut count = 0;
        while list.remove_data(|a, b| a == b, &val) {
            count += 1;
        }
        assert_eq!(count, 4);
        assert_eq!(list.length(), entries.len() - 5);

        let val = 89;
        assert!(list.remove_data(|a, b| a == b, &val));
        assert_eq!(list.length(), entries.len() - 6);
    }

    #[test]
    fn test_slist_sort() {
        let mut list = SList::new();
        let entries = [89, 4, 23, 42, 4, 16, 15, 4, 8, 99, 50, 30, 4];
        let sorted = [4, 4, 4, 4, 8, 15, 16, 23, 30, 42, 50, 89, 99];

        for &entry in &entries {
            list.prepend(entry);
        }

        list.sort(|a, b| a.cmp(b));

        assert_eq!(list.length(), sorted.len());

        for (i, &val) in sorted.iter().enumerate() {
            assert_eq!(list.nth_data(i), Some(&val));
        }
    }

    #[test]
    fn test_slist_find_data() {
        let mut list = SList::new();
        let entries = [89, 23, 42, 16, 15, 4, 8, 99, 50, 30];

        for &entry in &entries {
            list.append(entry);
        }

        for &entry in &entries {
            let result = list.nth_entry(0).unwrap();
            assert_eq!(result.data(), &entry);
        }

        let val = 0;
        assert!(list.nth_entry(0).is_none());

        let val = 56;
        assert!(list.nth_entry(0).is_none());
    }

    #[test]
    fn test_slist_to_array() {
        let mut list = SList::new();
        let variable1 = 50;
        let variable2 = 0;
        let variable3 = 0;
        let variable4 = 0;

        list.append(variable1);
        list.append(variable2);
        list.append(variable3);
        list.append(variable4);

        let array = list.to_array();
        assert_eq!(array[0], &variable1);
        assert_eq!(array[1], &variable2);
        assert_eq!(array[2], &variable3);
        assert_eq!(array[3], &variable4);
    }
}
